package medium;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 贪心+哈希表
 */
public class T12 {
    public static void main(String[] args) {

        System.out.println(intToRoman(3749));
    }


    public static String intToRoman(int num) {

        Map<Integer, String> v = new LinkedHashMap<>();
        v.put(1000,"M");
        v.put(900,"CM");
        v.put(500,"D");
        v.put(400,"CD");
        v.put(100,"C");
        v.put(90,"XC");
        v.put(50,"L");
        v.put(40,"XL");
        v.put(10,"X");
        v.put(9,"IX");
        v.put(5,"V");
        v.put(4,"IV");
        v.put(1,"I");

        StringBuffer roman = new StringBuffer();
        while (num>0){
            for (Map.Entry<Integer, String> entry : v.entrySet()) {
                if(num>=entry.getKey()){
                    roman.append(entry.getValue());
                    num-=entry.getKey();
                    break;
                }
            }
        }
        return roman.toString();
    }
}
